package leetcode_900;

import java.util.ArrayList;
import java.util.List;

/**
 *@author 周杨
 *GuessTheWord_843 猜单词游戏 每次会给反馈 请找出最佳猜策略
 *describe:用数组记录单词的差异度 AC 2%
 *see:https://leetcode.com/problems/guess-the-word/solution/
 *2018年11月2日 下午7:54:48
 */
public class GuessTheWord_843 {

	class Master {
		public int guess(String word) {
			return 1;
		};
	}

	int[][] H;

	public void findSecretWord(String[] wordlist, Master master) {
		int N = wordlist.length;
		H = new int[N][N];
		for (int i = 0; i < N; ++i)
			for (int j = i; j < N; ++j) {
				int match = 0;
				for (int k = 0; k < 6; ++k)
					if (wordlist[i].charAt(k) == wordlist[j].charAt(k))
						match++;
				H[i][j] = H[j][i] = match;
			}

		List<Integer> possible = new ArrayList();
		List<Integer> path = new ArrayList();
		for (int i = 0; i < N; ++i)
			possible.add(i);

		while (!possible.isEmpty()) {
			int guess = solve(possible, path);
			int matches = master.guess(wordlist[guess]);
			if (matches == wordlist[0].length())
				return;
			List<Integer> possible2 = new ArrayList();
			for (Integer j : possible)
				if (H[guess][j] == matches)
					possible2.add(j);
			possible = possible2;
			path.add(guess);
		}

	}

	public int solve(List<Integer> possible, List<Integer> path) {
		if (possible.size() <= 2)
			return possible.get(0);
		List<Integer> ansgrp = possible;
		int ansguess = -1;

		for (int guess = 0; guess < H.length; ++guess) {
			if (!path.contains(guess)) {
				ArrayList<Integer>[] groups = new ArrayList[7];
				for (int i = 0; i < 7; ++i)
					groups[i] = new ArrayList<Integer>();
				for (Integer j : possible)
					if (j != guess) {
						groups[H[guess][j]].add(j);
					}

				ArrayList<Integer> maxgroup = groups[0];
				for (int i = 0; i < 7; ++i)
					if (groups[i].size() > maxgroup.size())
						maxgroup = groups[i];

				if (maxgroup.size() < ansgrp.size()) {
					ansgrp = maxgroup;
					ansguess = guess;
				}
			}
		}

		return ansguess;
	}
}
